/**
 * describe:
 *
 * @author chaP
 * @date 2019/01/03
 */
package CodingTest;

import sun.reflect.generics.tree.Tree;

import java.util.*;
/**
 * 给定一个二叉树，返回其节点值自底向上的层次遍历。 （即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）

 例如：
 给定二叉树 [3,9,20,null,null,15,7],

 3
 / \
 9  20
 /  \
 15   7
 返回其自底向上的层次遍历为：

 [
 [15,7],
 [9,20],
 [3]
 ]
 */

public class levelOrderBottom {
    class TreeNode{
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int x){val = x;}
    }
    public List<List<Integer>> levelOrderBottom(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        if(root == null)
            return null;
        queue.add(root);
        while(queue.size() != 0){
           List<Integer> list = new ArrayList<Integer>();
            int len = queue.size();
            for(int i = 0;i<len;i++){
                TreeNode tmp = queue.poll();
                Integer tmp1 = tmp.val;
                list.add(tmp1);
                if(tmp.left != null)
                    queue.add(tmp.left);
                if(tmp.right != null)
                    queue.add(tmp.right);
            }
            res.add(list);
        }
        Collections.reverse(res);
        return res;
    }
}
